package edu.whu.rose.clock.kps.algorithm.blinks.search;

import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.algorithm.blinks.index.BilevelIndexDB;
import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockVertexKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks.index.KNEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.index.NKEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.index.PNEntry;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class BiLevelSearch {

	private BilevelIndexDB bidb;
	
	private double bound;
	
	private Date startTime; 
	long totalTime;
	public long indexTime;
	
	public BiLevelSearch(BilevelIndexDB bidb) {
		this.bidb = bidb;
	}
	
	public static void main(String[] args) {
		BilevelIndexDB bidb = new BilevelIndexDB();
		if (bidb.initEnv() && bidb.openDB()) {
			BiLevelSearch blinks = new BiLevelSearch(bidb);
			String[] keywords = new String[]{"victor", "congress"};
			int k = 10;
			
			Date startTime = new Date();
			SimpleAnswer[] answers = blinks.process(keywords, k);
			Date endTime = new Date();
			blinks.totalTime = endTime.getTime() - startTime.getTime();
			
			if (answers != null) {
				for (int i = 0; i < answers.length; i++) {
					SimpleAnswer at = answers[i];
					if (at == null) {
						break;
					}
					System.out.print("Rank " + (i + 1) + ": root[" + at.getRoot() + "] ");
					for (int j = 0; j < at.getLeafNumber(); j++) {
						int[] path = at.getPath(j);
						System.out.print("( ");
						if (path != null) {
							for (int m = 0; m < path.length; m++) {
								System.out.print(path[m] + ", ");
							}
						}
						System.out.print(" )");
					}
					System.out.println();
				}
				
				System.out.println("Total time exhausted: " + blinks.totalTime + " ms");
			}
			else {
				System.out.println("Sorry, no result is found.");
			}
			
			bidb.closeDB();
		}
	}
	
	public SimpleAnswer[] process(String[] keywords, int k) {
		startTime = new Date();
		try {
			ArrayList<PotentialTree> answers = new ArrayList<PotentialTree>();
			//------------------------------------------------------
			SimpleAnswer[] topk = new SimpleAnswer[k];
			int size = 0;
			//------------------------------------------------------
			
			GroupHeap[] heaps = new GroupHeap[keywords.length];
			
			HashMap<Integer, PotentialTree> trees = new HashMap<Integer, PotentialTree>();
			
			ArrayList<HashSet<Integer>> crossed = new ArrayList<HashSet<Integer>>();
			for (int i = 0; i < keywords.length; i++) {
				crossed.add(new HashSet<Integer>());
			}
			
			HashSet<Integer> abandoned = new HashSet<Integer>();
			
			int visitTime = 0;
			int repeatTime = 0;
			
			bound = Double.MAX_VALUE;
			
			double total = 0.0d;
			
			boolean first_k = true;
			
			Date date = null;
			
			// initialize heaps
			for (int i = 0; i < keywords.length; i++) {
				heaps[i] = new GroupHeap();
				date = new Date();
				int[] blockIds = bidb.getFromKeywordBlock(keywords[i]);
				indexTime += new Date().getTime() - date.getTime();
				for (int j = 0; j < blockIds.length; j++) {
					date = new Date();
					KNCursor knc = new KNCursor(blockIds[j], keywords[i], bidb);
					indexTime += new Date().getTime() - date.getTime();
					heaps[i].enqueue(knc);
				}
			}
			
			while (true) {
				// expand group by group
				for (int i = 0; i < keywords.length; i++) {
					Cursor cursor = heaps[i].dequeue();
					cursor.next();

					int block = cursor.getBlock();
					double distance = cursor.getDistance();
					int vertex = cursor.getNode();
					int knode = cursor.getKnode();
					int first = cursor.getFirst();
					
					// if abandoned
					if (abandoned.contains(new Integer(vertex))) {
						if (!cursor.empty()) {
							heaps[i].enqueue(cursor);
						}
						continue;
					}
					
					// visit current root
					visitTime++;
					boolean mark = true;
					PotentialTree tree = trees.get(new Integer(vertex));
					
					// the tree does not exist
					// produce a new tree at this root, and try forward connection to other group in this block
					if (tree == null) {
						tree = new PotentialTree(vertex, keywords.length);
						tree.setCursor(i, cursor);  // hold the predecessor information
						tree.setPredecessor(i, first);
						tree.setDistance(i, distance);
						tree.setD1(i, distance);
						date = new Date();
						double np = bidb.getFromVertexPortal(new SimpleSubgraphVertex(block, vertex));
						indexTime += new Date().getTime() - date.getTime();
						tree.setD2(np + 1.0d);
						for (int j = 0; j < keywords.length; j++) {
							if (j != i) {
								double nk = 0.0d;
								NKEntry nke = null;
								try {
									date = new Date();
									nke = bidb.getFromVertexKeyword(new BlockVertexKeyword(block, vertex, keywords[j]));
									indexTime += new Date().getTime() - date.getTime();
									if (nke == null) {
										continue;
									}
									else {
										nk = nke.getDistance();
										tree.setD1(j, nk);
									}
								}
								catch (DatabaseException ex) {
									ex.printStackTrace();
								}
								if (np >= nk) {
									date = new Date();
									tree.setCursor(j, new KNCursor(block, keywords[j], bidb));
									indexTime += new Date().getTime() - date.getTime();
									tree.setDistance(j, nk);
									tree.setPredecessor(j, nke.getFirst());
								}
							}
						}
						trees.put(new Integer(vertex), tree);
					}
					// the tree exists, but is over large and so will be abandoned
					else if (sumLBD(tree, heaps, block, keywords) >= bound) {
						abandoned.add(new Integer(vertex));
						trees.remove(new Integer(vertex));
						continue;
					}
					// the tree exists and is not over large, and has not been visited by this group
					else if (tree.getDistance(i) == Double.MAX_VALUE) {
						tree.setCursor(i, cursor);
						tree.setDistance(i, distance);
						tree.setPredecessor(i, first);
					}
					// the tree exists and is not over large, but has been visited by this group
					// I think the root should be a portal
					else {
						mark = false;
						repeatTime++;
					}

					if (mark) { // to determine if the tree has been inserted or modified
						if (tree.isAnswer()) {
//-------------------------------------------------------------------------------------------------------
							SimpleAnswer newAnswer = convert(tree);
							addTopKAnswer(newAnswer, topk, size);
//							addAnswer(answers, tree);
//*******************************************************************************************************
							
							abandoned.add(new Integer(vertex));
							trees.remove(new Integer(vertex));
							
//-------------------------------------------------------------------------------------------------------
							if (size == k) {
//							if (answers.size() >= k) {
//*******************************************************************************************************
								if (first_k) {
									Date firstk = new Date();
									System.out.println(
											"Time exhausted for producing first k answers: " + 
											(firstk.getTime() - startTime.getTime()) + "ms");
									System.out.println("Time exhausted for reading index: " + indexTime + "ms");
//-------------------------------------------------------------------------------------------------------
									double sum = 0.0d;
									for (int n = 0; n < topk.length; n++) {
										SimpleAnswer sa = topk[n];
										System.out.print("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
										System.out.print(" root[" + sa.getRoot() + "] ");
										sum += sa.getScore();
										for (int y = 0; y < sa.getLeafNumber(); y++) {
											int[] path = sa.getPath(y);
											System.out.print("( ");
											if (path != null) {
												for (int m = 0; m < path.length; m++) {
													System.out.print(path[m] + ", ");
												}
											}
											System.out.print(" )");
										}
										System.out.println();
									}
									System.out.println("Average score: " + (sum / k));
//*******************************************************************************************************
									first_k = false;
								}
//-------------------------------------------------------------------------------------------------------
								bound = topk[k - 1].getScore();
//								bound = answers.get(k - 1).sumDistances();
//*******************************************************************************************************
							}
						}
					}
					
					if (!crossed.get(i).contains(new Integer(vertex))) {
						int[] PBList = bidb.getFromPortalBlock(vertex);
						if (PBList != null) {
							crossed.get(i).add(new Integer(vertex));
							if (distance != 0.0d) {
								for (int j = 0; j < PBList.length; j++) {
									int ablock = PBList[j];
									if (ablock != block) {
										date = new Date();
//										PNCursor pnc = new PNCursor(ablock, vertex, distance, knode, bidb);
										PNCursor pnc = new PNCursor(ablock, cursor, bidb);
										indexTime += new Date().getTime() - date.getTime();
										if (!pnc.empty()) {
											heaps[i].enqueue(pnc);
										}
									}
								}
							}
						}
					}
					
					if (!cursor.empty()) {
						heaps[i].enqueue(cursor);
					}
					
					if (answers.size() >= k){
						// condition 1: total must be larger than bound
						if (total <= bound) {
							for (int j = 0; j < keywords.length; j++) {
								double top = heaps[j].top();
								if (top != -1.0d) {
									total += top;
								}
							}
							if (total <= bound) {
								continue;
							}
						}
						
						// condition 2: all trees have a lower bound larger than bound
						Iterator<Integer> it = trees.keySet().iterator();
						while (it.hasNext()) {
							Integer root = it.next();
							PotentialTree pt = trees.get(root);
							if (sumLBD(pt, heaps, block, keywords) < bound) {
//								break;
							}
							else {
								abandoned.add(root);
								it.remove();
							}
						}
						if (trees.size() > 0) {
							continue;
						}

						// stopping the algorithm
						SimpleAnswer[] result = new SimpleAnswer[k];
						Iterator<PotentialTree> it2 = answers.iterator();
						int x = 0;
						while (x < k && it2.hasNext()) {
							result[x] = convert(it2.next());
							x++;
						}
						System.out.println("Time exhausted for reading index: " + indexTime + "ms");
						return result;
					}
					
				}
			}
		}
		catch (DatabaseException ex) {
			ex.printStackTrace();
		}
		catch (UnsupportedEncodingException ex) {
			ex.printStackTrace();
		}
		System.out.println("Time exhausted for reading index: " + indexTime + "ms");
		return null;
	}
	
	private SimpleAnswer convert(PotentialTree pt) {
		int root = pt.getRoot();
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		int[] matched = pt.getMatcheds();
		int[][] paths = new int[pt.size()][];
		for (int i = 0; i < pt.size(); i++) {
			if (root != matched[i]) {
				paths[i] = getPath(root, pt.getCursor(i), allVertexes, matched[i]);
			}
		}
		return new SimpleAnswer(root, matched, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int root, Cursor cursor,
			SequentialIntArray allVertexes, int matched) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		while (!cursor.isKn()) {
			Object[] list = cursor.getList();
			int portal = ((PNCursor) cursor).getPortal();
			
			for (int j = list.length - 1; j >= 0; j--) {
				if (((PNEntry)list[j]).getNode() == current) {
					current = ((PNEntry)list[j]).getFirst();
					eia.add(current);
					allVertexes.insert(current);
					if (current == portal) {
						break;
					}
				}
			}
			
			cursor = ((PNCursor) cursor).getPreCursors();
		}
		
		Object[] list = cursor.getList();
		for (int j = list.length - 1; j >= 0; j--) {
			if (((KNEntry)list[j]).getNode() == current) {
				current = ((KNEntry)list[j]).getFirst();
				eia.add(current);
				allVertexes.insert(current);
				if (current == matched) {
					break;
				}
			}
		}
		
		return eia.toArray();
	}
	
	private double sumLBD(PotentialTree tree, GroupHeap[] heaps, int block, String[] keywords) {
		double sum = 0.0d;
		for (int i = 0; i < tree.size(); i++) {
			double distance = tree.getDistance(i);
			if (distance < Double.MAX_VALUE) {
				sum += distance;
			}
			else {
				double d1 = 0.0d;
				if (!heaps[i].isEmpty()) {
					d1 = heaps[i].top();
				}
				else {
					return Double.MAX_VALUE;
				}
				double d2 = Math.min(tree.getD1(i), tree.getD2());
				double d = Math.max(d1, d2);
				sum += d;
			}
		}
		return sum;
	}
	
	private void addAnswer(ArrayList<PotentialTree> answers, PotentialTree answer) {
		if (answers.size() == 0) {
			answers.add(answer);
			return;
		}
		
		int low = 0;
		int mid = 0;
		int top = answers.size() - 1;
		while (low <= top) {
			mid = (low + top) / 2;
			if (answer.compareTo(answers.get(mid)) > 0) {
				low = mid + 1;
			}
			else if (answer.compareTo(answers.get(mid)) < 0) {
				top = mid - 1;
			}
			else {
				answers.add(answers.get(answers.size() - 1));
				for (int i = answers.size() - 2; i > mid; i--) {
					answers.set(i, answers.get(i - 1));
				}
				answers.set(mid, answer);
				return;
			}
		}
		answers.add(answers.get(answers.size() - 1));
		for (int i = answers.size() - 2; i > low; i--) {
			answers.set(i, answers.get(i - 1));
		}
		answers.set(low, answer);
	}
	

	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

}
